{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Broken Calculator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: brokenCalc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #坏了的计算器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在显示着数字&nbsp;<code>startValue</code>&nbsp;的坏计算器上，我们可以执行以下两种操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>双倍（Double）：</strong>将显示屏上的数字乘 2；</li>\n",
    "\t<li><strong>递减（Decrement）：</strong>将显示屏上的数字减 <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定两个整数&nbsp;<code>startValue</code>&nbsp;和&nbsp;<code>target</code>&nbsp;。返回显示数字&nbsp;<code>target</code>&nbsp;所需的最小操作数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>startValue = 2, target = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>先进行双倍运算，然后再进行递减运算 {2 -&gt; 4 -&gt; 3}.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>startValue = 5, target = 8\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>先递减，再双倍 {5 -&gt; 4 -&gt; 8}.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>startValue = 3, target = 10\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>先双倍，然后递减，再双倍 {3 -&gt; 6 -&gt; 5 -&gt; 10}.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= startValue, target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [broken-calculator](https://leetcode.cn/problems/broken-calculator/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [broken-calculator](https://leetcode.cn/problems/broken-calculator/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3', '5\\n8', '3\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        # 正向最小==逆向最小；变小必须除，也就必须要求加到偶数\n",
    "        ans = 0\n",
    "        while target != startValue:\n",
    "            if target % 2:\n",
    "                target += 1\n",
    "                ans += 1\n",
    "            elif target < startValue:\n",
    "                ans += startValue - target\n",
    "                break\n",
    "            else:\n",
    "                target //= 2\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        if startValue >= target:\n",
    "            return startValue - target\n",
    "        count = 0\n",
    "        while target > startValue:\n",
    "            if target % 2 == 0:\n",
    "                target /= 2\n",
    "                count += 1\n",
    "            else:\n",
    "                target += 1\n",
    "                target /= 2\n",
    "                count += 2\n",
    "        count += int(startValue - target)\n",
    "        return count\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, X: int, Y: int) -> int:\n",
    "        if X >= Y:\n",
    "            return X - Y\n",
    "        ans = 0\n",
    "        while Y > X:\n",
    "            if Y & 1:\n",
    "                Y += 1\n",
    "            else:\n",
    "                Y //= 2\n",
    "            ans += 1\n",
    "        return ans + X - Y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        # 逆向思维 + 贪心\n",
    "        # 以最快的速度接近startValue,那就是target除2，分两种情况，奇数(加1再除2)或偶数(直接除2)\n",
    "        if startValue > target:\n",
    "            return startValue - target\n",
    "\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            # 如果是奇数就加一,然后再除二\n",
    "            if target % 2 == 1:\n",
    "                target = target + 1\n",
    "            else:\n",
    "                target /= 2\n",
    "        return int(ans + startValue - target)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        # ans 统计所需的操作次数\n",
    "        ans: int = 0\n",
    "        # 当 target 比 startValue 大时，要继续循环处理\n",
    "        while startValue < target:\n",
    "            if target & 1 == 0:\n",
    "                # 如果 target 是偶数，贪心地执行除以 2 操作\n",
    "                target >>= 1\n",
    "            else:\n",
    "                # 如果 target 是奇数，只能执行加 1 操作\n",
    "                target += 1\n",
    "\n",
    "            # 操作次数加 1\n",
    "            ans += 1\n",
    "\n",
    "        # 现在 startValue >= target ，\n",
    "        # 还需要对 target 执行 startValue - target 次加 1 操作，\n",
    "        # 才能得到 startValue\n",
    "        return ans + startValue - target "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def brokenCalc(self, X, Y):\n",
    "        ans = 0\n",
    "        while Y > X:\n",
    "            ans += 1\n",
    "            if Y%2: Y += 1\n",
    "            else: Y /= 2\n",
    "\n",
    "        return int(ans + X-Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        if startValue >= target:\n",
    "            return startValue - target\n",
    "        count = 0\n",
    "        while target > startValue:\n",
    "            if target % 2 == 0:\n",
    "                target /= 2\n",
    "                count += 1\n",
    "            elif target % 2 == 1:\n",
    "                target += 1\n",
    "                target /= 2\n",
    "                count += 2\n",
    "        count += int(startValue - target)\n",
    "        return count\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while startValue != target:\n",
    "            if startValue > target:\n",
    "                ans += startValue - target\n",
    "                break\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target = target // 2\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        if target < startValue:\n",
    "            return startValue - target\n",
    "        if target == startValue:\n",
    "            return 0\n",
    "        if target % 2 == 0:\n",
    "            return 1 + self.brokenCalc(startValue, target // 2)\n",
    "        if target % 2 == 1:\n",
    "            return 1 + self.brokenCalc(startValue, (target + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        operations = 0\n",
    "        while target > startValue:\n",
    "            operations += 1\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "        \n",
    "        return operations + (startValue - target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        if startValue >= target:\n",
    "            return startValue - target\n",
    "        count = 0\n",
    "        while target > startValue:\n",
    "            if target % 2 == 0:\n",
    "                target /= 2\n",
    "                count += 1\n",
    "            elif target % 2 == 1:\n",
    "                target += 1\n",
    "                target /= 2\n",
    "                count += 2\n",
    "        count += int(abs(target - startValue))\n",
    "        return count\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans=0\n",
    "        while target>startValue:\n",
    "            ans+=1\n",
    "            if target%2==1:\n",
    "                target+=1\n",
    "            else:\n",
    "                target//=2\n",
    "        print(ans)\n",
    "        return ans+startValue-target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        res = 0\n",
    "        while target>startValue:\n",
    "            if target%2==0:\n",
    "                target = target // 2\n",
    "            else:\n",
    "                target += 1\n",
    "            res += 1\n",
    "        return res + startValue - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        res = 0\n",
    "        while startValue < target:\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target = target // 2\n",
    "            res += 1\n",
    "        return res + (startValue-target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        l=0\n",
    "        ans=target\n",
    "        while ans!=startValue:\n",
    "            if ans<startValue:\n",
    "                return l+startValue-ans\n",
    "            if ans%2==0:\n",
    "                ans=ans//2\n",
    "            else:\n",
    "                ans+=1\n",
    "            l+=1\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, st: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > st:\n",
    "            if target & 1: \n",
    "                ans += 2\n",
    "                target = (target + 1) // 2\n",
    "            else:\n",
    "                ans += 1\n",
    "                target //= 2\n",
    "        return ans + st - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, st: int, target: int) -> int:\n",
    "        cont = 0\n",
    "        while st < target:\n",
    "            if target % 2 == 0:\n",
    "                target = target//2\n",
    "            else:\n",
    "                target = target+1\n",
    "            cont += 1\n",
    "        return cont + st - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        i=0\n",
    "        while target>startValue:\n",
    "            if target%2==0:\n",
    "                target/=2\n",
    "                i+=1\n",
    "            else:\n",
    "                target+=1\n",
    "                i+=1\n",
    "        return int(i+startValue-target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, X: int, Y: int) -> int:\n",
    "        i=0\n",
    "        while Y>X:\n",
    "            if Y%2==0:\n",
    "                Y//=2\n",
    "            else:\n",
    "                Y+=1\n",
    "            i+=1\n",
    "        return i+(X-Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        i = target\n",
    "        nums = []\n",
    "        while i > 1:\n",
    "            nums.append(i)\n",
    "            i = (i + 1) >> 1\n",
    "        nums.append(1)\n",
    "        nums.reverse()\n",
    "        n = len(nums)\n",
    "        # print(nums)\n",
    "        ans, i = inf, 0\n",
    "        while True:\n",
    "            if startValue >= target:\n",
    "                ans = min(ans, startValue - target + i)\n",
    "                break\n",
    "            else:\n",
    "                t = bisect_right(nums, startValue)\n",
    "                cur = i\n",
    "                cur += startValue - nums[t - 1]\n",
    "                for j in range(t, n):\n",
    "                    cur += 1 + nums[j] % 2\n",
    "                # print(cur)\n",
    "                startValue = startValue << 1\n",
    "                i += 1\n",
    "                ans = min(ans, cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def cal(startValue,target):\n",
    "    if target < startValue:\n",
    "        return startValue - target\n",
    "    if target == startValue:\n",
    "        return 0\n",
    "    if target % 2 == 0:\n",
    "        return 1 + cal(startValue, target // 2)\n",
    "    if target % 2 == 1:\n",
    "        return 1 + cal(startValue, (target + 1))\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        return  cal(startValue,target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            if target%2: target += 1\n",
    "            else: target /= 2\n",
    "\n",
    "        return int(ans + startValue-target)\n",
    "        '''\n",
    "        val = target\n",
    "        step = 0\n",
    "        while val != startValue:\n",
    "            print(val,startValue)\n",
    "            if startValue <= math.ceil(val/2):\n",
    "                if val % 2 != 0:\n",
    "                    val += 1\n",
    "                else:\n",
    "                    val /= 2\n",
    "            else:\n",
    "                val += 1\n",
    "            step += 1\n",
    "        return step\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, s: int, t: int) -> int:\n",
    "        cnt = 0 \n",
    "        while s < t:\n",
    "            if (t % 2) != 0:\n",
    "                t += 1\n",
    "            else:\n",
    "                t //= 2\n",
    "            cnt +=1\n",
    "        \n",
    "        return cnt + (s - t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        if startValue >= target:\n",
    "            return startValue - target\n",
    "        cnt_multiplication = 0\n",
    "        cnt_subtraction = 0\n",
    "        while startValue < target:\n",
    "            startValue *= 2\n",
    "            cnt_multiplication += 1\n",
    "        res_subtraction = startValue - target\n",
    "        ans = cnt_multiplication\n",
    "        while res_subtraction:\n",
    "            prod = pow(2, cnt_multiplication)\n",
    "            cnt_subtraction += res_subtraction // prod\n",
    "            res_subtraction %= prod\n",
    "            cnt_multiplication -= 1\n",
    "        return ans + cnt_subtraction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            if target%2: target += 1\n",
    "            else: target /= 2\n",
    "\n",
    "        return int(ans + startValue-target)\n",
    "        '''\n",
    "        val = target\n",
    "        step = 0\n",
    "        while val != startValue:\n",
    "            print(val,startValue)\n",
    "            if startValue <= math.ceil(val/2):\n",
    "                if val % 2 != 0:\n",
    "                    val += 1\n",
    "                else:\n",
    "                    val /= 2\n",
    "            else:\n",
    "                val += 1\n",
    "            step += 1\n",
    "        return step\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, st: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > st:\n",
    "            t = target & 1\n",
    "            ans += 1 + t\n",
    "            target = (target + t) // 2\n",
    "        return ans + st - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        operation_count = 0\n",
    "        while target > startValue:\n",
    "            # 如果 target 是奇数，先加 1 变成偶数\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                # 如果 target 是偶数，除以 2\n",
    "                target //= 2\n",
    "            operation_count += 1\n",
    "        return operation_count + (startValue - target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def brokenCalc(self, X, Y):\n",
    "        ans = 0\n",
    "        while Y > X:\n",
    "            ans += 1\n",
    "            if Y%2: Y += 1\n",
    "            else: Y //= 2\n",
    "\n",
    "        return ans + X-Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        result = 0\n",
    "        while target > startValue:\n",
    "            result += 1\n",
    "            if target % 2 == 0: target //= 2\n",
    "            else: target += 1\n",
    "        return result+startValue-target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans=0\n",
    "        while target>startValue:\n",
    "            ans+=1\n",
    "            if target%2:target+=1\n",
    "            else:target/=2\n",
    "        return int(ans+startValue-target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        s = startValue\n",
    "        t = target\n",
    "\n",
    "        while s < t:\n",
    "            if t % 2 == 1:\n",
    "                t += 1\n",
    "            else:\n",
    "                t //= 2\n",
    "            ans += 1\n",
    "\n",
    "        ans += s - t\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        res = 0\n",
    "        while startValue < target:\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target = target // 2\n",
    "            res += 1\n",
    "        return res + (startValue-target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        s = 0\n",
    "        while target != startValue:\n",
    "            while target > startValue:\n",
    "                if target % 2:\n",
    "                    target += 1\n",
    "                else:\n",
    "                    target //= 2\n",
    "                s += 1\n",
    "            else:\n",
    "                s += startValue - target\n",
    "                target += startValue - target            \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "        return ans + startValue - target\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 逆向思维，y可以加1或除以2，让y尽可能除2，最快地接近x\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        x, y = startValue, target\n",
    "        res = 0\n",
    "        while x < y:\n",
    "            if y % 2 == 0:\n",
    "                y //= 2\n",
    "                res += 1\n",
    "            else:\n",
    "                y = (y + 1) // 2\n",
    "                res += 2\n",
    "        return res + x - y\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            if target % 2 ==0 :\n",
    "                target = target // 2\n",
    "            else:\n",
    "                target += 1\n",
    "                \n",
    "        return ans + startValue - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, X: int, Y: int) -> int:\n",
    "        if X >= Y:\n",
    "            return X - Y\n",
    "        ans = 0\n",
    "        while Y > X:\n",
    "            if Y & 1:\n",
    "                Y += 1\n",
    "            else:\n",
    "                Y //= 2\n",
    "            ans += 1\n",
    "        return ans + X - Y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        \"\"\"\n",
    "        逆向思维：让target去逼近startValue 即变为target//2 或者+1\n",
    "        想要次数最小总是贪心执行出发\n",
    "        1.当target是偶数，先执行2次加法再执行1除法等价于先执行1除法再执行1次加法\n",
    "        2.当target是奇数，先执行3次加法再执行1除法等价于先执行1加1除1加\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        while target>startValue:\n",
    "            count += 1\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "        return count+startValue-target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        count=0\n",
    "        while target>startValue:\n",
    "            count+=1\n",
    "            if target%2==0:\n",
    "                target/=2\n",
    "            else:\n",
    "                target+=1\n",
    "        return int(count+startValue-target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, X: int, Y: int) -> int:\n",
    "        #Y只能除以2或者+1\n",
    "        res = 0\n",
    "        while X < Y:            #贪心\n",
    "            if Y % 2 == 1:\n",
    "                Y += 1\n",
    "            else:\n",
    "                Y //= 2\n",
    "            res += 1\n",
    "        return res + (X - Y)    #其余的差距，只能一个一个来\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            if target % 2:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "        return ans - target + startValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while startValue < target:\n",
    "            if target%2:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "            ans += 1\n",
    "        return ans + startValue - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while startValue < target:\n",
    "            if target % 2 == 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "            ans += 1\n",
    "        return ans + startValue - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            if target & 1:\n",
    "                target += 1\n",
    "            else:\n",
    "                target //= 2\n",
    "            ans += 1\n",
    "        return ans + startValue - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        # 逆过程，如果target是奇数，就+1，否则//2。直到target小于等于start\n",
    "        # 最后用加法填补最后的差距\n",
    "        res = 0\n",
    "        while target>startValue:\n",
    "            if target%2==0:\n",
    "                target = target // 2\n",
    "            else:\n",
    "                target += 1\n",
    "            res += 1\n",
    "        return res + startValue - target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans=0\n",
    "        while target>startValue:\n",
    "            ans+=1\n",
    "            if target%2==1:\n",
    "                target+=1\n",
    "            else:\n",
    "                target//=2\n",
    "        return ans-target+startValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0\n",
    "        while target > startValue:\n",
    "            ans += 1\n",
    "            if target % 2 == 0:\n",
    "                target //= 2\n",
    "            else:\n",
    "                target += 1\n",
    "        return ans + startValue - target "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans=0\n",
    "        while target>startValue:\n",
    "            if target%2:\n",
    "                target+=1\n",
    "            else:\n",
    "                target//=2\n",
    "            ans+=1\n",
    "        return ans+startValue-target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\r\n",
    "        # if target <= startValue:\r\n",
    "        #     return(startValue - target)\r\n",
    "        # lis = [0] * (target + 1)\r\n",
    "\r\n",
    "        # # 初始值\r\n",
    "        # for i in range(1, startValue + 1):\r\n",
    "        #     lis[i] = startValue - i\r\n",
    "\r\n",
    "        # for i in range(startValue + 1, target + 1):\r\n",
    "        #     if i % 2 == 0:\r\n",
    "        #         lis[i] = lis[i // 2] + 1\r\n",
    "        #     else:\r\n",
    "        #         lis[i] = lis[(i + 1) // 2] + 2\r\n",
    "        # return(lis[-1])\r\n",
    "\r\n",
    "        def answer(n):\r\n",
    "            if n <= startValue:\r\n",
    "                return(startValue - n)\r\n",
    "            if n % 2 == 0:\r\n",
    "                return(answer(n // 2) + 1)\r\n",
    "            else:\r\n",
    "                return(answer((n + 1) // 2) + 2)\r\n",
    "\r\n",
    "        return(answer(target))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, s: int, t: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        while s < t:\n",
    "            if t % 2 == 1:\n",
    "                t += 1\n",
    "            else:\n",
    "                t //= 2\n",
    "            ans += 1\n",
    "        \n",
    "        ans += s - t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brokenCalc(self, startValue: int, target: int) -> int:\n",
    "        ans = 0 \n",
    "        x, y = startValue, target\n",
    "        while x != y:\n",
    "            if x < y:\n",
    "                if y % 2 == 0:\n",
    "                    y //= 2\n",
    "                else:\n",
    "                    y += 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans += x - y\n",
    "                y += x - y \n",
    "                \n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
